{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lexicographically Smallest Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeSmallestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字典序最小回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>小写英文字母</strong> 组成的字符串 <code>s</code> ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 <strong>替换</strong>&nbsp; <code>s</code> 中的一个字符。</p>\n",
    "\n",
    "<p>请你执行 <strong>尽可能少的操作</strong> ，使 <code>s</code> 变成一个 <strong>回文串</strong> 。如果执行 <strong>最少</strong> 操作次数的方案不止一种，则只需选取 <strong>字典序最小</strong> 的方案。</p>\n",
    "\n",
    "<p>对于两个长度相同的字符串 <code>a</code> 和 <code>b</code> ，在 <code>a</code> 和 <code>b</code> 出现不同的第一个位置，如果该位置上 <code>a</code> 中对应字母比 <code>b</code> 中对应字母在字母表中出现顺序更早，则认为 <code>a</code> 的字典序比 <code>b</code> 的字典序要小。</p>\n",
    "\n",
    "<p>返回最终的回文字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"egcfe\"\n",
    "<strong>输出：</strong>\"efcfe\"\n",
    "<strong>解释：</strong>将 \"egcfe\" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 \"efcfe\"，只需将 'g' 改为 'f' 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\"\n",
    "<strong>输出：</strong>\"abba\"\n",
    "<strong>解释：</strong>将 \"abcd\" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 \"abba\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"seven\"\n",
    "<strong>输出：</strong>\"neven\"\n",
    "<strong>解释：</strong>将 \"seven\" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 \"neven\" 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lexicographically-smallest-palindrome](https://leetcode.cn/problems/lexicographically-smallest-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lexicographically-smallest-palindrome](https://leetcode.cn/problems/lexicographically-smallest-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"egcfe\"', '\"abcd\"', '\"seven\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        for i in range(n // 2):\n",
    "            j = n - 1 - i\n",
    "            if s[i] != s[j]:\n",
    "                if s[i] < s[j]:\n",
    "                    s[j] = s[i]\n",
    "                else:\n",
    "                    s[i] = s[j]\n",
    "        return ''.join(s)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def makeSmallestPalindrome(self, s):\n",
    "        return ''.join(min(x, y) for x, y in zip(s, s[::-1]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        news = list(s)\n",
    "        left = 0\n",
    "        right = len(news) - 1\n",
    "        while left <= right:\n",
    "            if news[left] == news[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                if news[left] < news[right]:\n",
    "                    news[right] = news[left]\n",
    "                    \n",
    "                else:\n",
    "                    news[left] = news[right]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        return \"\".join(news)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        ss=list(s)\n",
    "        ll = len(ss)\n",
    "        l= ll // 2\n",
    "        for i in range(l):\n",
    "            if ss[i]!=ss[ll-1-i]:\n",
    "                ch = min(ss[ll-1-i],ss[i])\n",
    "                ss[ll-1-i] = ch\n",
    "                ss[i] = ch\n",
    "        return ''.join(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        for i in range(len(s)//2):\n",
    "            x,y=s[i],s[-i-1]\n",
    "            if x>y:\n",
    "                s[i]=y\n",
    "            else:\n",
    "                s[-1-i]=x\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        left, right = 0 , len(s)-1\n",
    "        s = list(s)\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                if ord(s[left]) < ord(s[right]):\n",
    "                    s[right] = s[left]\n",
    "                else:\n",
    "                    s[left] = s[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x, y = s[i], s[-1 - i]\n",
    "            if x > y: s[i] = y\n",
    "            else: s[-1 - i] = x\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        for i in range(len(s)//2):\n",
    "            x,y=s[i],s[-i-1]\n",
    "            if x>y:\n",
    "                s[i]=y\n",
    "            else:\n",
    "                s[-1-i]=x\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        lst = [ch for ch in s]\n",
    "        l, r = 0, len(lst) - 1\n",
    "        while l < r:\n",
    "            if lst[l] < lst[r]:\n",
    "                lst[r] = lst[l]\n",
    "            elif lst[l] > lst[r]:\n",
    "                lst[l] = lst[r]\n",
    "            \n",
    "            l += 1\n",
    "            r -= 1\n",
    "        \n",
    "        return \"\".join(lst)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x, y = s[i], s[-1 - i]\n",
    "            if x > y: s[i] = y\n",
    "            else: s[-1 - i] = x\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        flag = len(s)//2\n",
    "        s = list(s)\n",
    "        for i in range(flag):\n",
    "            small = min(s[i],s[-1-i],key=ord)\n",
    "            s[i],s[-1-i] = small,small\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        l, r = 0, len(s) - 1\n",
    "        ans = \"\"\n",
    "        while l <= r:\n",
    "            if s[l] != s[r]:\n",
    "                if ord(s[l]) < ord(s[r]):\n",
    "                    ans += s[l]\n",
    "                elif ord(s[l]) > ord(s[r]):\n",
    "                    ans += s[r]\n",
    "            else:\n",
    "                ans += s[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        \n",
    "        return ans + ans[::-1] if len(s) % 2 == 0 else ans[:-1] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s_list = list(s)\n",
    "        for i in range(int(len(s) / 2)):\n",
    "            x, y = s_list[i], s_list[-i - 1]\n",
    "            if x > y:\n",
    "                s_list[i] = y\n",
    "            else:\n",
    "                s_list[-i - 1] = x\n",
    "        return ''.join(s_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return s\n",
    "        s = list(s)\n",
    "        cnt = 0\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low <= high:\n",
    "            if s[low] == s[high]:\n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                if s[low] < s[high]:\n",
    "                    s[high] = s[low]\n",
    "                else:\n",
    "                    s[low] = s[high]\n",
    "                cnt += 1\n",
    "        return \"\".join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def makeSmallestPalindrome(self, s: str) -> str:\n",
    "#         n=len(s)\n",
    "#         s=list(s)\n",
    "#         if n%2:\n",
    "#             i,j=n//2-1,n//2+1\n",
    "#         else:\n",
    "#             i,j=n//2-1,n//2\n",
    "#         while i>=0 and j<n:\n",
    "#             if s[i]!=s[j]:\n",
    "#                 m=min(s[i],s[j])\n",
    "#                 s[i],s[j]=m,m \n",
    "#             i-=1\n",
    "#             j+=1\n",
    "#         return \"\".join(s)\n",
    "\n",
    "### 灵茶山（变列表先）\n",
    "class Solution:\n",
    "\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "\n",
    "        s = list(s)\n",
    "\n",
    "        for i in range(len(s) // 2):\n",
    "\n",
    "            x, y = s[i], s[-1 - i]\n",
    "\n",
    "            if x > y: s[i] = y\n",
    "\n",
    "            else: s[-1 - i] = x\n",
    "\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s)//2):\n",
    "            x,y = s[i],s[-1-i]\n",
    "            if x>y:s[i] = y\n",
    "            else:s[-1-i] = x\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ls = list(s)\n",
    "        if n%2:\n",
    "            i = j = n // 2\n",
    "        else:\n",
    "            i = n//2-1\n",
    "            j = n//2\n",
    "        while i >= 0:\n",
    "            if ls[i] < ls[j]:\n",
    "                ls[j] = ls[i]\n",
    "            elif ls[i] > ls[j]:\n",
    "                ls[i] = ls[j]\n",
    "            i -= 1\n",
    "            j += 1\n",
    "        return \"\".join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x, y = s[i], s[-1 - i]\n",
    "            if x > y: s[i] = y\n",
    "            else: s[-1 - i] = x\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        flag = len(s)//2\n",
    "        s = list(s)\n",
    "        for i in range(flag):\n",
    "            small = min(s[i],s[-1-i],key=ord)\n",
    "            s[i],s[-1-i] = small,small\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ans = \"\"\n",
    "        for i in range(n // 2):\n",
    "            ans += min(s[:n // 2][i], s[n - 1 - n // 2:][::-1][i])\n",
    "        return ans + ans[::-1] if n % 2 == 0 else ans + s[n // 2] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        lo, hi = 0, len(s)-1\n",
    "        s = list(s)\n",
    "        while lo<hi:\n",
    "            if s[lo] == s[hi]:\n",
    "                lo += 1\n",
    "                hi -= 1\n",
    "                continue\n",
    "            if s[lo] < s[hi]:\n",
    "                s[hi] = s[lo]\n",
    "            else:\n",
    "                s[lo] = s[hi]\n",
    "            lo += 1\n",
    "            hi -= 1\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        ans=0\n",
    "        s=list(s)\n",
    "        left,right=0,len(s)-1\n",
    "        while left<right:\n",
    "            if s[left]!=s[right]:\n",
    "                s[left]=s[right]=min(s[left],s[right])\n",
    "                ans+=1\n",
    "            left+=1\n",
    "            right-=1\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        #双指针\n",
    "        n = len(s)\n",
    "        ls = list(s)\n",
    "        if n==1:\n",
    "            return s\n",
    "        left,right = 0,n-1\n",
    "        while left<right:\n",
    "            if ls[left]!=ls[right]:\n",
    "                if ls[left]<ls[right]:\n",
    "                    ls[right] = ls[left]\n",
    "                else:\n",
    "                    ls[left] = ls[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ''.join(ls)\n",
    "\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s) // 2\n",
    "        ans = \"\"\n",
    "        left = s[:n]\n",
    "        right = s[len(s) - 1 - n:][::-1]\n",
    "        for i in range(n):\n",
    "            ans += min(left[i], right[i])\n",
    "        return ans + ans[::-1] if len(s) % 2 == 0 else ans + s[n] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        return ''.join(min(x, y) for x, y in zip(s, s[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        S=list(s)\n",
    "        i,j=0,n-1\n",
    "        while i<j:\n",
    "            if S[i]!=S[j]:\n",
    "                S[i],S[j]=min(S[i],S[j]),min(S[i],S[j])\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return ''.join(S)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)-1\n",
    "        i=0\n",
    "        ans=\"\"\n",
    "        while i<=n:\n",
    "            first=s[i]\n",
    "            last=s[n]\n",
    "            if first==last:\n",
    "                if i==n:\n",
    "                    ans=ans[:i]+first+ans[i:]\n",
    "                else:\n",
    "                    ans = ans[:i]+first+last+ans[i:]\n",
    "            else:\n",
    "                first=min(first,last)\n",
    "                ans = ans[:i]+first+first+ans[i:]\n",
    "            i += 1\n",
    "            n -= 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s_f = s[::-1]\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if s[i] > s_f[i]:\n",
    "                res.append(s_f[i])\n",
    "            else:\n",
    "                res.append(s[i])\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        return ''.join(min(s[i], s[-i - 1]) for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        # s = list(s)\n",
    "        # n = len(s)\n",
    "        # left, right = 0, n-1\n",
    "        # while left<=right:\n",
    "        #     if s[left]!=s[right]:\n",
    "        #         if s[left]<s[right]:\n",
    "        #             s[right] = s[left]\n",
    "        #         else:\n",
    "        #             s[left] = s[right]\n",
    "        #     left += 1\n",
    "        #     right -= 1\n",
    "        # return ''.join(s)\n",
    "\n",
    "        n = len(s)\n",
    "        left, right = 0, n-1\n",
    "        ss = list(s)\n",
    "        while left<=right:\n",
    "            if ss[left]!=ss[right]:\n",
    "                if ss[left]<ss[right]:\n",
    "                    ss[right]=ss[left]\n",
    "                else:\n",
    "                    ss[left]=ss[right]\n",
    "            left += 1 \n",
    "            right -= 1\n",
    "        return \"\".join(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        left , right = 0 , n-1\n",
    "        result = list(s)\n",
    "        while left < right:\n",
    "            if result[left] != result[right]:\n",
    "                if result[left] < result[right]:\n",
    "                    result[right] = result[left]\n",
    "                else:\n",
    "                    result[left] = result[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)//2\n",
    "        list_s=list(s)\n",
    "        a,b=0,len(s)-1\n",
    "        for i in range(n):\n",
    "            if list_s[a]!=list_s[b]:\n",
    "                if list_s[a]>list_s[b]:\n",
    "                    list_s[a]=list_s[b]\n",
    "                else:\n",
    "                    list_s[b]=list_s[a]\n",
    "            a,b=a+1,b-1\n",
    "        return ''.join(list_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        while i<=j:\n",
    "            if s[i]!=s[j]:\n",
    "                if s[i]<s[j]:\n",
    "                    s=list(s)\n",
    "                    s[j]=s[i]\n",
    "                    s=''.join(s)\n",
    "                if s[i]>s[j]:\n",
    "                    s=list(s)\n",
    "                    s[i]=s[j]\n",
    "                    s=''.join(s)\n",
    "            j-=1\n",
    "            i+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s1,s2,l = '','',len(s)\n",
    "        for i in range(l//2):\n",
    "                s1 += min(s[i],s[l-i-1])\n",
    "                s2 = min(s[i],s[l-i-1]) + s2\n",
    "        if not l % 2:\n",
    "            return s1 + s2\n",
    "        return s1 + s[l//2] + s2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x,y = s[i],s[-1 - i]\n",
    "            if x > y: s[i] = y\n",
    "            else: s[-1 - i] = x \n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        result=\"\"\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            temp = s[i] if s[i] < s[n-i-1] else s[n-i-1]\n",
    "            result = result + temp\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        for i in range(int(len(s) / 2)):\n",
    "            if s[i] != s[-i - 1]:\n",
    "                temp_str = '' if i == 0 else s[-i:]\n",
    "                if ord(s[i]) - ord(s[-i - 1]) < 0:\n",
    "                    s = s[:-i - 1] + s[i] + temp_str\n",
    "                else:\n",
    "                    s = s[:i] + s[-i - 1] + s[i + 1:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x, y = s[i], s[-1 - i]\n",
    "            if x > y: s[i] = y\n",
    "            else: s[-1 - i] = x\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str: \n",
    "\n",
    "        # 双指针 \n",
    "\n",
    "        # 如果字符串只有一个字母，则一定是回文串，直接返回原字符串\n",
    "        if len(s) == 1: \n",
    "            return s \n",
    "        \n",
    "        letters = list(s)   # 字符串不可修改，所以先转换成列表 \n",
    "        left, right = 0, len(s)-1    # 初始化双指针 \n",
    "        count = 0 # 如果需要记录修改字母的次数，则初始化计数变量 \n",
    "\n",
    "        while left <= right: \n",
    "            # 如果两个字母一样，则移动两个指针\n",
    "            if letters[left] == letters[right]:     \n",
    "                left += 1 \n",
    "                right -= 1 \n",
    "            # 如果两个字母不一样，则判断两个字母在字母表中的位置\n",
    "            else: \n",
    "                # 如果左侧的字母在字母表中的位置排在右侧字母之前，则将右侧字母替换成左侧字母\n",
    "                if letters[left] < letters[right]:  \n",
    "                    letters[right] = letters[left] \n",
    "                else: \n",
    "                    letters[left] = letters[right] \n",
    "                # 如果需要记录修改字母的次数 \n",
    "                count += 1 \n",
    "        return ''.join(letters)   # 将列表转换成字符串\n",
    "\n",
    "        ''' \n",
    "        作者：L181_3\n",
    "        链接：https://leetcode.cn/problems/lexicographically-smallest-palindrome/solutions/2277813/shuang-zhi-zhen-fa-bian-li-yi-ci-by-l181-w0zm/\n",
    "        ''' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        left, right = 0, n - 1\n",
    "        ans = [\"a\"] * n\n",
    "        while left <= right:\n",
    "            c = min(s[left], s[right])\n",
    "            ans[left] = ans[right] = c\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        k=list(s)\n",
    "        while i<=j:\n",
    "            if k[i]!=k[j]:\n",
    "                if k[i]<k[j]:\n",
    "                    k[j]=k[i]\n",
    "                if k[i]>k[j]:\n",
    "                    k[i]=k[j]\n",
    "            j-=1\n",
    "            i+=1\n",
    "        k=''.join(k)\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        return \"\".join(min(s[i], s[~i]) for i in range(len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s)//2):\n",
    "            x,y = s[i],s[-1-i]\n",
    "            if x>y:s[i]=y\n",
    "            else:s[-1-i]=x\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        for i in range(len(s)//2):\n",
    "            left,right=s[i],s[-1-i]\n",
    "            if left>right:s[i]=right\n",
    "            else:s[-1-i]=left\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "\n",
    "        # 计算需要变动的次数\n",
    "        changes = 0\n",
    "        for i in range(n // 2):\n",
    "            if s[i] != s[n - i - 1]:\n",
    "                changes += 1\n",
    "\n",
    "        # 调整字符的顺序，使得变动的次数最小\n",
    "        for i in range(n // 2):\n",
    "            if s[i] != s[n - i - 1]:\n",
    "                s[i] = s[n - i - 1] = min(s[i], s[n - i - 1])\n",
    "\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        l, r = 0, len(s) - 1\n",
    "        ans = \"\"\n",
    "        while l <= r:\n",
    "            if s[l] != s[r]:\n",
    "                if ord(s[l]) < ord(s[r]):\n",
    "                    ans += s[l]\n",
    "                elif ord(s[l]) > ord(s[r]):\n",
    "                    ans += s[r]\n",
    "            else:\n",
    "                ans += s[l]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        \n",
    "        return ans + ans[::-1] if len(s) % 2 == 0 else ans[:-1] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        a=s[:len(s)//2]\n",
    "        b = s[len(s)//2:][::-1]\n",
    "        res = ''\n",
    "        for i in range(len(a)):\n",
    "            if a[i]!=b[i]:\n",
    "                res +=chr(min(ord(a[i]),ord(b[i])))\n",
    "            else:\n",
    "                res +=a[i]\n",
    "        if len(s) % 2 ==0:\n",
    "            return res+res[::-1]\n",
    "        else:\n",
    "            return res+s[len(s)//2] + res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            s[i] = s[~i] = s[i] if s[i] < s[~i] else s[~i]\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "        ans = \"\"\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                if ord(s[left]) <= ord(s[right]):\n",
    "                    ans += s[left]\n",
    "                else:\n",
    "                    ans += s[right]\n",
    "            else:\n",
    "                ans += s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        mid =\"\"\n",
    "        if len(s) % 2 != 0:\n",
    "            mid = s[len(s) // 2]\n",
    "\n",
    "        return ans + mid + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x, y = s[i], s[-1 - i]\n",
    "            if x > y :\n",
    "                s[i] = y\n",
    "            else:\n",
    "                s[-1 - i] = x\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return s\n",
    "        s = list(s)\n",
    "        cnt = 0\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low <= high:\n",
    "            if s[low] == s[high]:\n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                if s[low] < s[high]:\n",
    "                    s[high] = s[low]\n",
    "                else:\n",
    "                    s[low] = s[high]\n",
    "                cnt += 1\n",
    "        return \"\".join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        # 将字符串转换为列表，方便修改\n",
    "        chars = list(s)\n",
    "        left, right = 0, len(chars) - 1\n",
    "        changes = 0\n",
    "\n",
    "        while left < right:\n",
    "            if chars[left] != chars[right]:\n",
    "                # 将较大的字符更改为较小的字符\n",
    "                if chars[left] > chars[right]:\n",
    "                    chars[left] = chars[right]\n",
    "                else:\n",
    "                    chars[right] = chars[left]\n",
    "                changes += 1\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        return ''.join(chars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s) // 2\n",
    "        left, right = s[:n], s[len(s) - 1 - n:][::-1]\n",
    "        ans = \"\".join([min(left[i], right[i]) for i in range(n)])\n",
    "        return ans + ans[::-1] if len(s) % 2 == 0 else ans + s[n] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        ans,l = '',len(s)\n",
    "        for i in range(l//2):\n",
    "            ans += min(s[i],s[l-i-1])\n",
    "        if not l % 2:\n",
    "            return ans + ans[::-1]\n",
    "        return ans + s[l//2] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        #双指针\n",
    "        n = len(s)\n",
    "        ls = list(s)\n",
    "        if n==1:\n",
    "            return s\n",
    "        left,right = 0,n-1\n",
    "        while left<right:\n",
    "            if ls[left]!=ls[right]:\n",
    "                if ls[left]<ls[right]:\n",
    "                    ls[right] = ls[left]\n",
    "                else:\n",
    "                    ls[left] = ls[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ''.join(ls)\n",
    "\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        i, j = 0, len(s)-1\n",
    "        s = [c for c in s]\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                if ord(s[i]) < ord(s[j]):\n",
    "                    s[j] = s[i]\n",
    "                else:\n",
    "                    s[i] = s[j]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ans = \"\"\n",
    "        left = s[:n // 2]\n",
    "        right = s[n - 1 - n // 2:][::-1]\n",
    "        for i in range(n // 2):\n",
    "            ans += min(left[i], right[i])\n",
    "        return ans + ans[::-1] if n % 2 == 0 else ans + s[n // 2] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n % 2 == 0:\n",
    "            s1 = s[:n//2]\n",
    "            s2 = s[n//2:]\n",
    "        else:\n",
    "            s1 = s[:(n-1)//2]\n",
    "            s2 = s[(n-1)//2+1:]\n",
    "        s2 = s2[::-1]\n",
    "        sNew = ''\n",
    "        for i in range(len(s2)):\n",
    "            c1 = s1[i]\n",
    "            c2 = s2[i]\n",
    "            if c1 == c2:\n",
    "                sNew += c1\n",
    "            else:\n",
    "                if ord(c1) > ord(c2):\n",
    "                    sNew += c2\n",
    "                else:\n",
    "                    sNew += c1\n",
    "        if n % 2 == 0:\n",
    "            return sNew + sNew[::-1]\n",
    "        else:\n",
    "            return sNew + s[(n-1)//2] + sNew[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        left, right = 0, len(s) - 1\n",
    "        s = list(s)\n",
    "        while left < right:\n",
    "            s_left, s_right = s[left], s[right]\n",
    "            if s_left > s_right:\n",
    "                s[left] = s_right\n",
    "            elif s_left < s_right:\n",
    "                s[right] = s_left\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        a =''\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        while i<j:\n",
    "            if s[i]!=s[j]:\n",
    "                if s[i]>=s[j]:\n",
    "                    a+=s[j]\n",
    "                else:\n",
    "                    a+=s[i]\n",
    "            else:\n",
    "                a+=s[i]\n",
    "            i+=1\n",
    "            j-=1\n",
    "        ans = a\n",
    "        if len(s)%2==1:\n",
    "            ans += s[i]\n",
    "        ans += a[::-1]\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "      s = list(s)\n",
    "      n = len(s)\n",
    "      for i in range(n // 2):\n",
    "        if s[i] != s[-i-1]:\n",
    "          if s[i] < s[-i-1]:  s[-i-1] = s[i]\n",
    "          else: s[i] = s[-i-1]\n",
    "      return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s_list = list(s)\n",
    "        s_rev = list(s[::-1])\n",
    "        # print(s_rev)\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        for k, v in zip(s_list, s_rev):\n",
    "            if k == v:\n",
    "                res.append(k)\n",
    "            if k != v and k > v:\n",
    "                res.append(v)\n",
    "            if k != v and k < v:\n",
    "                res.append(k)\n",
    "        # print(res)\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        ans,l = '',len(s)\n",
    "        for i in range(l//2):\n",
    "            ans += min(s[i],s[l-i-1])\n",
    "        if not l % 2:\n",
    "            return ans + ans[::-1]\n",
    "        return ans + s[l//2] + ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        j = len(s) -1\n",
    "        i = 0\n",
    "        temp = list(s)\n",
    "        while (i < j):\n",
    "            if temp[i] != temp[j]:\n",
    "                if ord(temp[i]) < ord(temp[j]):\n",
    "                    temp[j] = temp[i]\n",
    "                else:\n",
    "                    temp[i] = temp[j]\n",
    "            i +=1\n",
    "            j -=1\n",
    "        return ''.join(temp)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)  # 将字符串转换为可变的列表\n",
    "        length = len(s)\n",
    "        left = 0\n",
    "        right = length - 1\n",
    "        \n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                if s[left] < s[right]:\n",
    "                    s[right] = s[left]\n",
    "                else:\n",
    "                    s[left] = s[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "            \n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[~i]:\n",
    "                s[i] = s[~i] = s[i] if s[i] < s[~i] else s[~i]\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        i, j = 0, len(s)-1\n",
    "        x = ''\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                x += s[i] if s[i] < s[j] else s[j]\n",
    "            else:\n",
    "                x += s[i]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i == j:\n",
    "            return x + s[i] + x[::-1]\n",
    "        else:\n",
    "            return x + x[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        s=list(s)\n",
    "        if n%2:\n",
    "            i,j=n//2-1,n//2+1\n",
    "        else:\n",
    "            i,j=n//2-1,n//2\n",
    "        while i>=0 and j<n:\n",
    "            if s[i]!=s[j]:\n",
    "                m=min(s[i],s[j])\n",
    "                s[i],s[j]=m,m \n",
    "            i-=1\n",
    "            j+=1\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        res = ''\n",
    "        for i in range(length//2):\n",
    "            if s[i] < s[length - i - 1]:\n",
    "                res += s[i]\n",
    "            else:\n",
    "                res += s[length - i - 1]\n",
    "        if length % 2:\n",
    "            res = res + s[length // 2] + res[::-1]\n",
    "        else:\n",
    "            res += res[::-1]\n",
    "        return res\n",
    "'''\n",
    "2697. 字典序最小回文串\n",
    "提示\n",
    "简单\n",
    "11\n",
    "相关企业\n",
    "给你一个由 小写英文字母 组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 替换  s 中的一个字符。\n",
    "请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小 的方案。\n",
    "对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。\n",
    "返回最终的回文字符串。\n",
    "示例 1：\n",
    "输入：s = \"egcfe\"\n",
    "输出：\"efcfe\"\n",
    "解释：将 \"egcfe\" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 \"efcfe\"，只需将 'g' 改为 'f' 。\n",
    "示例 2：\n",
    "输入：s = \"abcd\"\n",
    "输出：\"abba\"\n",
    "解释：将 \"abcd\" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 \"abba\" 。\n",
    "示例 3：\n",
    "输入：s = \"seven\"\n",
    "输出：\"neven\"\n",
    "解释：将 \"seven\" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 \"neven\" 。\n",
    "提示：\n",
    "1 <= s.length <= 1000\n",
    "s 仅由小写英文字母组成\n",
    "通过次数\n",
    "8K\n",
    "提交次数\n",
    "9.8K\n",
    "通过率\n",
    "82.3%'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            return s\n",
    "        if n%2==1:\n",
    "            center=n//2\n",
    "            ans=s[center]\n",
    "            for i in range(1,n//2+1):\n",
    "                if s[center-i]!=s[center+i]:\n",
    "                    t=min(s[center-i],s[center+i],key=lambda x:ord(x))\n",
    "                    # print(t)\n",
    "                    ans=t+ans+t\n",
    "                else:\n",
    "                    ans=s[center-i]+ans+s[center-i]\n",
    "            return ans\n",
    "        else:\n",
    "            ans=\"\"\n",
    "            center_right=n//2\n",
    "            center_left=n//2-1\n",
    "            for i in range(n//2):\n",
    "                \n",
    "                if s[center_left-i]!=s[center_right+i]:\n",
    "                    t=min(s[center_left-i],s[center_right+i],key=lambda x:ord(x))\n",
    "                    # print(t)\n",
    "                    ans=t+ans+t\n",
    "                else:\n",
    "                    ans=s[center_left-i]+ans+s[center_left-i]\n",
    "            return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        k=list(s)\n",
    "        while i<j:\n",
    "            if k[i]!=k[j]:\n",
    "                if k[i]<k[j]:\n",
    "                    k[j]=k[i]\n",
    "                if k[i]>k[j]:\n",
    "                    k[i]=k[j]\n",
    "            j-=1\n",
    "            i+=1\n",
    "        k=''.join(k)\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        lst = list(s)\n",
    "        t = lst[:n // 2]\n",
    "        r = lst[n - 1 - n // 2:][::-1]\n",
    "        for i in range(n // 2):\n",
    "            if r[i] != t[i]:\n",
    "                if t[i] > r[i]:\n",
    "                    lst[i] = r[i]\n",
    "                else:\n",
    "                    lst[n - i - 1] = t[i]\n",
    "        return \"\".join(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        n=len(s)\n",
    "        left=0\n",
    "        right=n-1\n",
    "        while left<right:\n",
    "            a=s[left]\n",
    "            b=s[right]\n",
    "            if a==b:\n",
    "                left+=1\n",
    "                right-=1\n",
    "                continue\n",
    "\n",
    "            if a<b:\n",
    "                s[right]=a\n",
    "            else:\n",
    "                s[left]=b\n",
    "            left+=1\n",
    "            right-=1\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s=list(s)\n",
    "        for i in range(len(s)//2):\n",
    "            j=len(s)-1-i\n",
    "            if s[i]<s[j]:\n",
    "                m=s[i]\n",
    "            else:\n",
    "                m=s[j]\n",
    "            s[i],s[j]=m,m\n",
    "        return ''.join(s)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\r\n",
    "        alp = [chr(i) for i in range(97,123)]\r\n",
    "        s = list(s)\r\n",
    "        for i in range(int(len(s)/2)):\r\n",
    "            if s[i] != s[-i-1]:\r\n",
    "                if alp.index(s[i]) < alp.index(s[-i-1]):\r\n",
    "                    s[-i-1] = s[i]\r\n",
    "                else:\r\n",
    "                    s[i] = s[-i-1]\r\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        ns,l = list(s),len(s)\n",
    "        for i in range(l//2):\n",
    "            if ns[i] < ns[l-1-i]:\n",
    "                ns[l-1-i] = ns[i]\n",
    "            elif ns[i] > ns[l-1-i]:\n",
    "                ns[i] = ns[l-1-i]\n",
    "        return ''.join(ns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s) // 2):\n",
    "            x, y = s[i], s[-1 - i]\n",
    "            if x > y: s[i] = y\n",
    "            else: s[-1 - i] = x\n",
    "        return ''.join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSmallestPalindrome(self, s: str) -> str:\n",
    "        half = int(len(s)/2)\n",
    "        \n",
    "        left = 0\n",
    "        right = 0\n",
    "        count = 0\n",
    "        index = 0\n",
    "        \n",
    "        res = [\"0\"]*len(s)\n",
    "        \n",
    "        for i in range(0, half+1):\n",
    "            if s[len(s)-i-1] != s[i]:\n",
    "                if ord(s[i]) < ord(s[-i-1]):\n",
    "                    res[i] = s[i]\n",
    "                    res[-i-1] = s[i]\n",
    "                else:\n",
    "                    res[i] = s[-i-1]\n",
    "                    res[-i-1] = s[-i-1]\n",
    "            else:\n",
    "                res[i] = s[i]\n",
    "                res[-i-1] = s[i]\n",
    "                \n",
    "        ans = \"\"    \n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            ans = ans + res[i]\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
